package com.gitee.wsl.ext.array


fun <T> Array<T>.heapifyDown(index: Int, actualSize: Int, comparator: Comparator<in T>) {
    val leftChildIndex = index * 2 + 1
    if (leftChildIndex >= actualSize) {
        return
    }

    val rightChildIndex = leftChildIndex + 1

    val childIndex =
        if (rightChildIndex >= actualSize) {
            leftChildIndex
        } else {
            val leftChildValue = get(leftChildIndex)
            val rightChildValue = get(rightChildIndex)
            if (comparator.compare(leftChildValue, rightChildValue) < 0) leftChildIndex else rightChildIndex
        }

    if (comparator.compare(get(childIndex), get(index)) < 0) {
        swap(index, childIndex)
        heapifyDown(childIndex, actualSize, comparator)
    }
}

fun <T> Array<T>.heapifyUp(index: Int, comparator: Comparator<in T>) {
    val parentIndex = if (index % 2 == 0) index / 2 - 1 else index / 2
    if (parentIndex < 0) {
        return
    }

    if (comparator.compare(get(parentIndex), get(index)) > 0) {
        swap(index, parentIndex)
        heapifyUp(parentIndex, comparator)
    }
}